import java.util.*;

/**
 * 210. 课程表 II
 * https://leetcode-cn.com/problems/course-schedule-ii/
 */
public class Solutions_210 {
    public static void main(String[] args) {
//        int numCourses = 2;
//        int[][] prerequisites = {{1, 0}};  // output: {0, 1}

        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        // output: {0, 1, 2, 3} or {0, 2, 1, 3}

        int[] result = findOrder(numCourses, prerequisites);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 广度优先搜索-bfs
     */
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        int idx = 0;
        // needCount[1] = 1：学习课程 1 需要先完成 1 门课程
        int[] course = new int[numCourses];
        // list.get(0).add(1)，完成课程 0 后，可以学习课程 1
        List<List<Integer>> list = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] arr : prerequisites) {
            // arr[0] 需要先完成的课程数量加 1
            course[arr[0]] ++;
            list.get(arr[1]).add(arr[0]);
        }
        for (int i = 0; i < course.length; i++) {
            if (course[i] == 0) {
                // 记录下不需要先修其他课程的课程，入度为 0 的课程
                queue.add(i);
            }
        }
        if (queue.isEmpty()) {
            return new int[0];
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 能够学完的课程减 1
                numCourses --;
                int j = queue.poll();
                // 添加到学习顺序中
                res[idx++] = j;
                List<Integer> ok = list.get(j);
                for (int k : ok) {
                    // 完成课程 j 后，需要完成课程 j 的那些课程的需要完成课程数量减 1
                    course[k] --;
                    if (course[k] == 0) {
                        // k 课程可以学习了
                        queue.add(k);
                    }
                }
            }
        }
        // 最终，numCourses 个课程都能够学完，返回学习顺序
        return numCourses == 0 ? res : new int[0];
    }
}
